Stochastic Subgradient Algorithms for Strongly Convex Optimization over Distributed Networks

摘要

We study diffusion and consensus based optimization of a sum of unknownconvex objective functions over distributed networks. The only access to thesefunctions is through stochastic gradient oracles, each of which is onlyavailable at a different node, and a limited number of gradient oracle calls isallowed at each node. In this framework, we introduce a convex optimizationalgorithm based on the stochastic gradient descent (SGD) updates. Particularly,we use a carefully designed time-dependent weighted averaging of the SGDiterates, which yields a convergence rate of$O\left(\frac{N\sqrt{N}}{T}\right)$ after $T$ gradient updates for each node ona network of $N$ nodes. We then show that after $T$ gradient oracle calls, theaverage SGD iterate achieves a mean square deviation (MSD) of$O\left(\frac{\sqrt{N}}{T}\right)$. This rate of convergence is optimal as itmatches the performance lower bound up to constant terms. Similar to the SGDalgorithm, the computational complexity of the proposed algorithm also scaleslinearly with the dimensionality of the data. Furthermore, the communicationload of the proposed method is the same as the communication load of the SGDalgorithm. Thus, the proposed algorithm is highly efficient in terms ofcomplexity and communication load. We illustrate the merits of the algorithmwith respect to the state-of-art methods over benchmark real life data sets andwidely studied network topologies.